This invention relates to digital computing devices which generate sequences of numerical values, e.g., sequences of memory addresses. Circuits for this purpose are commonly incorporated into "block transfer controllers" and similar input/output controllers for peripheral devices attached to a digital data processing system as well as into the logic by which arithmetic processors access their supporting memories. The class of computing devices incorporating circuits similar to block transfer controllers includes array processors.
The apparatus commonly used for generating such sequences of numerical values has the capability to generate sequential numerical values beginning at a given value and increasing (or decreasing), by a fixed increment, either a specified number of times or until a specified limit is reached or exceeded (e.g., 17, 18, 19, . . . , 1229). If a more complicated sequence of integer values is to be generated (e.g., 17, 18, 19, 25, 26, 27, 33, 34, 35, . . . , 81, 82, 83) in which a second increment (6, i.e., the difference between 19 and 25) is used whenever the first increment (1, i.e., the difference between 17 and 18) has been used a certain number of times (or more generally, when two or more increments--positive or negative or zero--are to be used in order each after the preceding increment in order has been used a characteristic number of times) the capability of most such circuits will be exceeded because of the amount of computing hardware or computing time that is required.
Thus, when apparatus for generating such sequences is required, the desired sequence is broken up into a number of subsequences each using a single increment. A central processing unit, or some other programmable processing unit, initializes a sequencing circuit for such subsequences. Such intervention by a separately-programmed processing unit has the effect of reducing the speed with which such complicated sequences of numerical values can be generated. Direct methods for generating such sequences of numerical values are known, but they are relatively complex and have structural characteristics which limit their speed.
A class of numerical sequences which can be advantageously generated by the invention described below are those with values defined by the formula of Equation A: ##EQU1## where numbers W.sub.0,W.sub.1, . . . ,W.sub.k are any arbitrary weights, i.e., constants, which determine, by means to be described later (see equation B, known to the art) the increments between successive values of the numerical sequence to be generated, where the numbers X.sub.j are non-negative integer indicies with each integer X.sub.j being in the range 0.ltoreq.X.ltoreq.R.sub.j -1 for some specified integer R.sub.j which is referred to as the radix of X.sub.j, and where the set of indicies EQU (X.sub.k, X.sub.k -1, . . . , X.sub.2, X.sub.1)
progresses through a sequence of values starting with some value (most commonly all zeros) and changing as the digits of a counter. To illustrate, a three digit counter of this type with radicies (2, 5, 3) would sequence through the following sets of index values:
______________________________________ X.sub.3 X.sub.2 X.sub.1 ______________________________________ 0 0 0 0 0 1 0 0 2 0 1 0 0 1 1 0 1 2 0 2 0 . . . 0 4 2 1 0 0 . . . 1 4 2 0 0 0 ______________________________________
where the last two lines illustrate the counter reaching its maximum value (142) and then resetting to the initial value.
The procedure will be seen to be somewhat similar to a common odometer except the radicies are 2, 5, and 3 in the example set forth above, instead of 10, 10, and 10 as in the case of an odometer. Thus, such a sequence of index values is equivalent to the state of a multidigit counter in which different digits may have different maximum values. As with an odometer, there are many states in the counting sequence at which two or more digits change at the same time. More specifically, when any digit of the counter is incremented, the all more-frequently-changing digits (if any) are simultaneously reset to zero. This makes it necessary either to have sufficient hardware to change all digits as necessary or to take extra time to change the several digits sequentially.
Counter circuits using binary logic often count backwards starting with the "largest" count (142 in the example) as illustrated below.
______________________________________ X.sub.3 X.sub.2 X.sub.1 ______________________________________ 1 4 2 1 4 1 1 4 0 1 3 2 1 3 1 1 3 0 1 2 2 1 2 1 . . . 1 0 0 0 4 2 0 4 1 . . . 0 0 0 1 4 2 ______________________________________
Such backwards counters are known to be--in principle, as opposed to specific function--equivalent to normal forward counters. Like forward counting counters, such backwards counters also experience changes of two or more digits between many states. Specifically when a counter digit decreases then all more-frequently-changing digits are reset to their maximum values.
For a specific set of radicies (R.sub.j) and a specific set of weights (W.sub.j) each set of index values yields a specific element of the resulting numerical sequence Z.
If weights W.sub.0 =6, W.sub.1 =2, W.sub.2 =-1, W.sub.3 =5 are specified, then using Equation A, the incrementing counter illustrated above generates the following numerical sequence:
______________________________________ 6 + 2 .multidot. 0 + (-1) .multidot. 0 + 5 .multidot. 0 = 6 6 + 2 .multidot. 1 + (-1) .multidot. 0 + 5 .multidot. 0 = 8 6 + 2 .multidot. 2 + (-1) .multidot. 0 + 5 .multidot. 0 = 10 6 + 2 .multidot. 0 + (-1) .multidot. 1 + 5 .multidot. 0 = 5 6 + 2 .multidot. 1 + (-1) .multidot. 1 + 5 .multidot. 0 = 7 6 + 2 .multidot. 2 + (-1) .multidot. 1 + 5 .multidot. 0 = 9 6 + 2 .multidot. 0 + (-1) .multidot. 2 + 5 .multidot. 0 = 4 6 + 2 .multidot. 1 + (-1) .multidot. 2 + 5 .multidot. 0 = 6 . . . 6 + 2 .multidot. 2 + (- 1) .multidot. 4 + 5 .multidot. 0 = 6 6 + 2 .multidot. 0 + (-1) .multidot. 0 + 5 .multidot. 1 = 11 . . . 6 + 2 .multidot. 2 + (-1) .multidot. 4 + 5 .multidot. 1 ______________________________________ = 11
Since when a digit is incremented, all more-frequently-changing digits are reset to zero, the difference between the numerical sequence values associated with two consecutive states is equal to the weight assigned to the least-frequently-changing digit which changes between those two states less the sum of the products of the maximum value of each other changing digit with the weights assigned to the corresponding digits. Thus, the effect of incrementing X.sub.1 is to increase the numerical sequence value by W.sub.1 =2; the effect of incrementing X.sub.2 is to increase the numerical sequence value by W.sub.2 -2.multidot.W.sub.1 =-5, and the effect of incrementing X.sub.3 is to increase the numerical sequence value by W.sub.3 -2.multidot.W.sub.1 -4.multidot.W.sub.2 =5-2.multidot.2-4.multidot.(-1)=5. The effect of decrementing these digits in a decrementing counter with the same weights is to decrease the numerical sequence value by the amounts of increase mentioned above for the incrementing mode.
The circuitry necessary to generate a sequence of numerical values by the addition of properly chosen increments (either positive, negative or zero) is known to be much simpler than to generate the same sequence by directly evaluating Equation A.